
/**
 * 
 * 生成哈夫曼树
 * 
 * 给定长度为 n 的无序的数字数组，每个数字代表二叉树的叶子节点的权值，数字数组的值均大于等于1。

请完成一个函数，根据输入的数字数组，生成哈夫曼树，并将哈夫曼树按照中序遍历输出。

为了保证输出的二叉树中序遍历结果统一，增加以下限制：

二叉树节点中，左节点权值小于右节点权值，根节点权值为左右节点权值之和。当左右节点权值相同时，左子树高度小于等于右子树高度。
注意：

所有用例保证有效，并能生成哈夫曼树。
提醒：

哈夫曼树又称为最优二叉树，是一种带权路径长度最短的二叉树。
所谓树的带权路径长度，就是树中所有的叶节点的权值乘上其到根节点的路径长度（若根节点为 0 层，叶节点到根节点的路径长度为叶节点的层数）
输入描述
例如：由叶子节点：5 15 40 30 10，生成的最优二叉树如下图所示，该树的最短带权路径长度为：40 * 1 + 30 * 2 + 15 * 3 + 5 * 4 + 10 * 4 = 205。



输出描述
输出一个哈夫曼树的中序遍历数组，数值间以空格分隔
 

用例
输入	5
5 15 40 30 10
输出	40 100 30 60 15 30 5 15 10
说明	根据输入，生成哈夫曼树，按照中序遍历返回。所有节点中，左节点权值小于等于右节点权值之和。当左右节点权值相同时，左子树高度小于右子树。结果如上图所示。

 */

import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringJoiner;

/**
  * 
  题目解析
本题主要是考察哈夫曼树的构建。

哈夫曼树定义：

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
比如题目用例给出的N个叶子节点的权值分别为：5 15 40 30 10

那么我们可以根据这些叶子节点任意构造一个二叉树，比如下图所示



那么这颗二叉树的各个叶子节点的带权路径长度如下：



5*3 + 15*3 + 40*3 + 30*3 + 10*1 = 280

因此这颗二叉树的带权路径长度 = 280 要比题目描述中构造的最优二叉树的205大。因此这种二叉树就不是哈夫曼树。

哈夫曼树是根据给定的n个叶子节点构造出的带权路径长度最短的二叉树。

而哈夫曼的构建是有固定思路：

首先，我们从给定的n个叶子节点的权值序列中取出最小的两个，

比如 [5, 15, 40, 30, 10] 中最小的两个是5、10，取出进行合并，则可得如下新节点15（绿色），



然后将新节点重新加入到权值序列中，得到红框中新序列 [15, 15, 40, 30] 

然后再从新序列 [15, 15, 40, 30]中取出最小的两个，进行合并



然后再从新序列 [30, 40, 30]中取出最小的两个，进行合并



然后再从新序列 [60, 40]中取出最小的两个，进行合并



此时序列中只剩下一个节点，即可停止上面逻辑。

按照这种策略构造出来的二叉树的带权路径长度是最短的，即构建出来的是哈夫曼树。

另外，如果初始有N个叶子节点的话，那么构造出来的哈夫曼树的节点总数就有 2 * N - 1 个。

其实，我们通过上图就可以发现规律，蓝色节点是初始N个叶子节点，绿色节点是新建的，而绿色节点的个数 = N - 1。

了解了哈夫曼树的构造原理后，其实本题就很简单了，只需要不停从给定的权值序列中：

取出两个最小的权值
放回两个最小权值的合并和
直到权值序列中只有一个元素时停止。

而上面取出两个最小、返回合并和后重新排序，这种行为是非常适合使用优先队列（小顶堆）做的。

Java和Python有内置的优先队列实现，而JS和C没有，因此JS和C可以尝试更简单的每次对权值序列进行降序排序，尾部两个就是最小的，放回合并和后再重新降序排序。

下面博客实现中，JS和C手撕优先队列，关于优先队列的原理可以看：

LeetCode - 1705 吃苹果的最大数目-CSDN博客

解析中对于优先队列实现剖析。

另外本题说：

为了保证输出的二叉树中序遍历结果统一，增加以下限制：

二叉树节点中，左节点权值小于右节点权值，根节点权值为左右节点权值之和。当左右节点权值相同时，左子树高度小于等于右子树高度。
我的想法是定义哈夫曼树节点，带上一个节点对应子树的高度值，即节点定义如下：

{
    left_child: ,   // 左子节点
    right_child: ,  // 右子节点
    weight: ,       // 当前节点权值
    height:         // 当前节点对应子树的高度
}
这样优先队列遇到相同权值的节点时，可以继续比较节点子树高度，高度低的优先级更高。

这样取出来的两个节点，第一个取出的肯定作为左子节点，第二个取出的肯定作为右子节点。

但是这种策略无法保证构造出来的哈夫曼树是唯一的，比如下面例子：

4
80 80 20 60
我可以构造出两种哈夫曼树，这两种哈夫曼树的带权路径长度是一样的



且这两种哈夫曼树都能满足：

二叉树节点中，左节点权值小于右节点权值，根节点权值为左右节点权值之和。当左右节点权值相同时，左子树高度小于等于右子树高度。
之所以会产生两种哈夫曼树，是因为当20、60合并后，新的权值序列中会有3个80



此时，如果一个绿色和一个蓝色优先合并，则得到



如果两个蓝色优先合并，则得到



这该咋搞？期望考试用例不会出现这种摸棱两可的情况。

2024.03.03



之前逻辑中，根据上面这句话，我错误地认为题目要求的哈夫曼树必然成立：右子树高度 ≥ 左子树高度。

其实上面这句话，仅在：左右子树权值相同时，需要确保：右子树高度 ≥ 左子树高度。

即，在左右子树权值不一样时，按照上面要求，则必然是：左子树权值 < 右子树权值，

此时，左子树高度 是有可能 大于 右子树高度的，比如下图



因此，下面逻辑中，我们父节点取高度值时，不能武断地认为是 rc.height + 1，而应该是 max(lc.height, rc.height) + 1。

2024.8.3

由于JS和C没有内置的优先队列实现类，但是手撕优先队列，代码量太大，所以这里增加一种有序数组解法，可以减少代码量，实现和优先队列一样的效果，但是性能更差一点。

  */
public class 生成哈夫曼树 {
    
    public static void main(String[] args) {
        
        try{

            Scanner scanner = new Scanner(System.in);
            //数组长度
            int len = scanner.nextInt();
            //将哈夫曼树节点进行排序，方便后面筛选出权值最小的两个节点
            PriorityQueue<TreeNode> priorityQueue = 
            new PriorityQueue<>((a,b) -> 

            // 题目说：当左右节点权值相同时，左子树高度小于等于右子树高度。因此当节点权重相同时，再按照节点子树高度升序
            a.weight != b.weight ? a.weight - b.weight : a.heigth - b.heigth

            );

            //解析数组节点
            for(int n=0; n<len; n++){
                int weight = scanner.nextInt();

                TreeNode node = new TreeNode(null, null, weight, 0);

                //添加节点
                priorityQueue.offer(node);

            }

            //初始n个节点经过多轮合并，只剩一个节点时，那么该节点就是哈夫曼树的根节点，因此当优先队列中只剩一个节点时即可停止合并
            while (priorityQueue.size() > 1) {
                //取出优先队列中前两个权值最小的节点，由于优先队列已按照 [节点权重，节点子树高度] 升序优先级，因此先出来的肯定是权重小，或者高度小的节点，即作为新节点的左子树
                TreeNode leftNode = priorityQueue.poll();
                TreeNode rightNode = priorityQueue.poll();

                //将lc和rc合并，合并后新节点fa的权重，是两个子节点权重之和，fa子树高度 = rc子树高度+1; PS：rc的高度>=lc的高度
                int fatherWeight = leftNode.weight + rightNode.weight;
                //int fa_height = rc.height + 1; // 这行逻辑有问题，但是实际考试可以满分
                //存在一些情况下，左子树权值小于右子树权值，但是左子树高度大于右子树高度，即不一定总是rc高度>=lc高度
                int fatherHeigth = Math.max(leftNode.heigth, rightNode.heigth)+1;

                TreeNode parentNode = new TreeNode(leftNode, rightNode, fatherWeight, fatherHeigth);

                priorityQueue.offer(parentNode);
            }



            //最后优先队列中必然只剩一个节点，即哈夫曼树的根节点，此时对此根节点（哈夫曼树）进行中序遍历
            TreeNode rootNode = priorityQueue.poll();

            StringJoiner stringJoiner = new StringJoiner(" ");

            handleOrder(rootNode, stringJoiner);

            System.out.println(stringJoiner.toString());

        }catch(Exception e){
            e.printStackTrace();
        }

    }

    private static void handleOrder(TreeNode treeNode, StringJoiner stringJoiner){

        if(null!=treeNode.leftNode){
            handleOrder(treeNode.leftNode, stringJoiner);
        } 

        stringJoiner.add(""+treeNode.weight);
        
        if(null!=treeNode.rightNode){
            handleOrder(treeNode.rightNode, stringJoiner);
        } 


    }

    //构建huffman 树节点
    private static class TreeNode {
    
        public TreeNode leftNode;
        public TreeNode rightNode;
        public int weight;
        public int heigth;

        public TreeNode(TreeNode leftNode, TreeNode rightNode, int weight, int heigth){

            this.leftNode = leftNode;
            this.rightNode = rightNode;
            this.weight = weight;
            this.heigth = heigth;
        }
        
    }
}
